package learn;

import java.util.Scanner;

public class quicksort {
   public static void main(String[] args) {
            //读取数据
       int[] arr={7,3,6,8,4,11,2,5,7,5,10,40,10,31,23,43,65,12,4,5};
            System.out.println("初始数组:");
            show(arr);
            quickSort(0,arr.length-1,arr,1);
            System.out.println("\n排序后");
            show(arr);
        }
    static void show(int[] arr){
            for(int i=0;i<arr.length;i++){
                System.out.print(arr[i]+" ");
            }
    }
    static void quickSort(int l,int r,int[] arr,int count){
        //双指针扫描法快排

        if(l>=r)return;

        int x=arr[l];
        int i=l-1;
        int j=r+1;
        while(i<j){
            //当还没扫描完
            do i++;while(arr[i]<x);//找到大于x的数字
            do j--;while(arr[j]>x);//找到小于x的数字
            if(i<j){//符合条件则交换
                arr[i]^=arr[j];
                arr[j]^=arr[i];
                arr[i]^=arr[j];
            }
        }

        if(count==1){ System.out.print("\n第一次排序");show(arr);}
        //此时,(l,j)和(j+1,r)两个集合是相等有序的，即左侧的数均小于右侧
        quickSort(l,j,arr,2);
        quickSort(j+1,r,arr,2);
    }




//    import java.util.Scanner;
//    public class Main {
//        static int[] arr;
//        static  int n;
//        public static void main(String[] args) {
//            //读取数据
//            Scanner in=new Scanner(System.in);
//            n=in.nextInt();
//            arr=new int[n];
//            for(int i=0;i<n;i++){
//                arr[i]=in.nextInt();
//            }
//            quickSort(arr,0,n-1);
//            for(int i=0;i<n;i++){
//                System.out.print(arr[i]+" ");
//            }
//        }
//        //快排模板
//        static void quickSort(int[] arr,int l,int r){
//            if(l>=r)return;
//            int x=arr[l],i=l-1,j=r+1;
//            while(i<j){
//                do i++;while (arr[i]<x);
//                do j--;while(arr[j]>x);
//                if(i<j){
//                    int temp=arr[i];
//                    arr[i]=arr[j];
//                    arr[j]=temp;
//                }
//            }
//            quickSort(arr,l,j);
//            quickSort(arr,j+1,r);
//        }
//    }
}
